Boys decided to prepare presents for girls on a holiday of
8th of March. When they were preparing presents, they quickly put there a
congratulation postcard and a soft toy. But when they began to put mandarins,
they came face to face with a trouble. At first they wanted to put m mandarins in every package (and in other packages –
apples), but they couldn’t do it because in one package were m – 1
mandarins. When they decided to put m – 1 mandarins, m – 2
mandarins left. Then they decided to put m – 2 mandarins, but m – 3
mandarins left, and so on. When they decided to put 2
mandarins, then 1 mandarin left. How many mandarins did the boys buy?
Input. The number of mandarins m
(1
< m ≤ 1000),
that the boys wanted to put initially into the presents.
Output. The minimum possible number of mandarins, that the
boys bought as a gift for the girls.
|
Sample input |
Sample output |
|
4 |
11 |
mathematics
The answer to the problem is the
value a = LCM(1, 2, 3, …, m) – 1. When you divide the number a by i
(2 ≤ i ≤ m), the residue will be i – 1, as required in the problem.
Store
all numbers from 1 to m in array t. We
show how to find a
= LCM(t1, t2, …, tn), performing the minimum number of operations on
large numbers (the value à is large).
Iterate through all pairs (ti,
tj), i < j, calculate for
each pair the value d = GCD(ti, tj), and divide tj
by d. After this operation the
product of all remaining values ti
equals to à.
Algorithm realization
Read the value m and
put the number i into the i-th cell of array t.
scanf("%d",&m);
for(i = 1; i
<= m; i++) t[i] = i;
After completing the double
loop the value LCM(1, 2, 3,
…, m) equals
to the product of numbers in array t. The function gcd calculates the greatest common divisor of two numbers.
for(i = 1; i
<= m; i++)
for(j = i+1; j
<= m; j++)
{
d = gcd(t[i],t[j]);
t[j] /= d;
}
Calculate the product of
numbers in array t using long arithmetic.
a =
BigInteger(t[1]);
for(i = 1; i
<= m; i++) a = a * t[i];
Subtract one from a and print the result.
a--;
a.print();printf("\n");
Java realization
import java.util.*;
import java.math.*;
public class Main
{
public static void main(String[] args)
{
Scanner con = new
Scanner(System.in);
int n = con.nextInt();
BigInteger res = BigInteger.ONE;
for(int i = 1; i <= n; i++)
{
BigInteger x = BigInteger.valueOf(i);
// res = res
* x / gcd(res,x)
res = res.multiply(x).divide(res.gcd(x));
}
res = res.subtract(BigInteger.ONE);
System.out.println(res);
con.close();
}
}
Java realization – long multiplication
import java.util.*;
import java.math.*;
public class Main
{
public static int gcd(int a, int b)
{
return (b == 0) ? a : gcd(b,a % b);
}
public static void main(String[] args)
{
Scanner con = new
Scanner(System.in);
int m = con.nextInt();
int t[] = new int[m+1];
for(int i = 1; i <= m; i++)
t[i] = i;
for(int i = 1; i <= m; i++)
for(int j = i + 1; j <= m; j++)
{
int d = gcd(t[i],t[j]);
t[j] /= d;
}
BigInteger res = BigInteger.ONE;
for(int i = 1; i <= m; i++)
res = res.multiply(BigInteger.valueOf(t[i]));
res = res.subtract(BigInteger.ONE);
System.out.println(res);
con.close();
}
}